package com.leetcode.easy;

/**
 * @Classname SolutionMerge
 * @Description 合并两个有序数组
 * @Date 2020/8/26 15:23
 * @Created by zfl
 */
public class SolutionMerge {
    /*
    *@Description 引入第三个表，将第一个表复制到第三个表中，然后对比。 单指针
    *@param [nums1, m, nums2, n]
    *@return void
    * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    * 内存消耗：39.8 MB, 在所有 Java 提交中击败了58.00%的用户
    */
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int[] nums = new int[m];
        /*for (int i = 0; i < m; i++) {
            nums[i] = nums1[i];
        }*/
        //上述功能可以用系统合并函数代替
        System.arraycopy(nums1, 0, nums, 0, m);
        int count = 0;
        for (int i = 0, j = 0; count < m + n;) {
            if (i < m && j < n) {
                if (nums[i] > nums2[j]) {
                    nums1[count++] = nums2[j++];
                } else {
                    nums1[count++] = nums[i++];
                }
            } else if (i < m && j >= n) {
                nums1[count++] = nums[i++];
            } else if(i >= m && j < n) {
                nums1[count++] = nums2[j++];
            }
        }
        for (int num : nums1) {
            System.out.print(num + " ");
        }
    }
    /*
    *@Description 双指针法 时间复杂度O(m + n),空间复杂度O(1)
    *@param [nums1, m, nums2, n]
    *@return void
    */
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        while((p1 >= 0) && (p2 >= 0))
            nums1[p--] = nums1[p1] < nums2[p2] ? nums2[p2--] : nums1[p1];
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1 );
    }
}
